package 春招冲刺百题计划;

import java.util.*;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-24
 * Time:19:12
 */

/**
 * 春招冲刺百题计划:373. 查找和最小的 K 对数字
 * 中等
 * 相关企业
 * 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
 * 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
 * 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
 * 示例 1:
 * 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
 * 输出: [1,2],[1,4],[1,6]
 * 解释: 返回序列中的前 3 对数：
 *      [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
 */
public class kSmallestPairs {
    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
//        int[] nums1 = {1,1,2};
//        int[] nums2 = {1,2,3};
        int k = 3;
        kSmallestPairs(nums1,nums2,k);
    }
    static List<List<Integer>> res;

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(k, (a, b) -> nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]);
        // 这个时候我们的索引就开始配对了
        // 开始配对
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            queue.add(new int[]{i, 0});
        }
        // 我们开始加入这里面
        // 我们添加
        List<List<Integer>> listlist = new ArrayList<>();
        while (true) {
            if (listlist.size() == k) {
                break;
            }
            int xiao[] = queue.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[xiao[0]]);
            list.add(nums2[xiao[1]]);
            listlist.add(list);
            // 首先我们不知道，要是数量不一样的结果是什么
            // 1,7,11
            // 2,4,6
            // 因为里面还有7,7的时候就判断1,2，加入1,4看看哪个小，到最后都加入了
            //因为在上面构建queue时就已经写好了不管是[1,0]还是[0,1]都是此时最小的在队顶所以不管是
            //[1,0],[2,0],[0,1]还是[0,1],[1,0],[2,0]都是一样的，都是为了得到最小的list服务的
            if (xiao[1] + 1 < nums2.length) {
                queue.add(new int[]{xiao[0], xiao[1] + 1});
            }

        }
        return listlist;
    }
}
